package q343_integerBreak;

import java.util.Arrays;

public class Solution_1 {
    /**
     * 这道题也是动态规划的问题
     * 首先我们考虑 dp数组的设计 dp[i] 应该将 i 拆分后能够得到最大的乘积
     * 那么是否 dp [i] 应该来自于 从 0 - i 之间所有的数 dp[j] 与 dp[i - j] 乘积
     *
     * 实际上 我们只需要考虑 j 与 dp[i - j] 即可 因为其会遍历0 - i
     * dp[i - j] 代表i - j拆分后最大乘积 使用Math.max(j * dp[i - j], j * (i - j))
     * 代表如果将i - j拆分后得到积大于不拆分 那就用大的 否则不如不拆分 直接用j * (i - j)
     */
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 0);
        for (int i = 2; i <= n; i++) {

            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(Math.max(j * dp[i - j], j * (i - j)), dp[i]);
            }
        }
        return dp[n];
    }
}
